package cn.fxzhang.leetcode.no14;

/**
 * 1442. 形成两个异或相等数组的三元组数目
 * a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
 * b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
 * 请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
 * 1 <= arr.length <= 300
 * 类型：枚举
 * 题解：枚举
 * 时间复杂度：O(N^3)
 * 空间复杂度：O(N^2)
 *
 * 提交记录(1/1)：
 * 执行用时: 48 ms, 击败了10.38%
 * 内存消耗: 37.3 MB, 击败了12.74%
 *
 * 【中等】通过次数24,570提交次数31,190
 * @author 张晓帆
 * @date 2021/5/18
 */
public class P1442_Count_Triplets_That_Can_Form_Two_Arrays_Of_Equal_Xor {

    public int countTriplets(int[] arr) {
        int n = arr.length;
        int[][] f = new int[n][n];
        for (int i=0; i<n; i++){
            f[i][i] = arr[i];
            for (int j =i+1; j<n; j++){
                f[i][j] = f[i][j-1]^arr[j];
            }
        }
        int total = 0;
        for (int i=0; i<n-1; i++){
            for (int j=i+1; j<n; j++){
                for (int k=j; k<n; k++){
                    if (f[i][j-1] == f[j][k]){
                        total++;
                    }
                }
            }
        }
        return total;
    }
}
